The invention generally relates to a system for buffering packets in a packet-switched digital communications device. More particularly, the invention relates to a buffering system and related method for use at a queueing point in a communications device which employs a multi-class, connection-orientated, communications protocol such as an asynchronous transfer mode (ATM) communications protocol.
Packet-switching communication devices which effect statistical multiplexing, such as ATM network nodes or switches, typically store in the same memory buffer all packets which need to be transmitted over a given link or line. The amount or size of the memory buffer is fixed, and thus an important issue relates to how the memory should be managed to ensure that traffic flows such as virtual circuit connections are provided with some degree of xe2x80x98fairnessxe2x80x99 in the use of this limited resource. The situation is further complicated in ATM networks since a connection can be associated with one of a variety of traffic classes, which have varying QoS requirements, and connections within a particular ATM traffic class can be set up with various cell loss ratios (a QoS characteristic). Thus, the memory should be managed to at least provide minimum guaranteed quality of service (QoS) to the various traffic classes, as well as optimal use of the memory above and beyond the minimum QoS. It should be noted that the memory used in such devices typically tends to be very fast, and very expensive, state-of-the-art devices, thereby precluding the option of merely adding more and more memory.
A common prior art buffer management scheme is to xe2x80x9chard partitionxe2x80x9d the memory, by allocating one fixed portion of a memory buffer to each traffic class. Thus, when a partition group is full, cells belonging to the corresponding traffic class are discarded. While this approach is easy to implement and can operate very quickly, its primary disadvantage is that buffer space which has been allocated to other traffic classes but otherwise unused at that instant is not employed, such that an opportunity is lost to provide service to that connection above and beyond the minimum QoS guarantee. In effect, hard partitioning the memory makes it difficult to take advantage of the bursty nature of many types of digital communications.
At the other extreme, using a finitely sized memory in an unregulated manner so that it is completely shared amongst the various connections, e.g., on a first-come first-served basis, could lead to starvation situations. This is also due to the bursty nature of digital traffic, which could potentially cause temporary buffer congestion. In addition, it is not possible to prioritize memory use in such a shared buffer system to ensure that minimum QoS guarantees are met for particular types of traffic flows.
Thus, system designers often have to balance the sharing of physical resources between various types of digital traffic and the isolation thereof. On the one hand, it is desired to share the memory buffer as much as possible in order to minimize the cost thereof, on the other hand, it is desired to isolate the flow of one virtual connection or group thereof so as to prevent the impact or influence of same on other virtual connections.
The invention seeks to facilitate this balance between the sharing of physical memory resources amongst distinct and various types of traffic flows and the logical isolation thereof. One aspect of the invention provides a buffering system for use in a digital communications device, comprising a memory for storing messages, such as packets or cells, and a controller connected to the memory for determining whether to store or discard messages based on predetermined discard criteria. The controller also includes means for storing messages in the memory and building the requisite queueing structures. In the system, the memory is logically partitioned into plural reserved buffer spaces allocated to predetermined groups of traffic flows (hereinafter xe2x80x9ctraffic groupsxe2x80x9d) and a shared buffer space. The controller is enabled to logically fill each reserved buffer space up to a predetermined state of congestion before logically storing messages belonging to the corresponding traffic group in the shared buffer space.
In the preferred embodiment, each traffic group is associated with a bound on its utilization of the shared buffer space. The bound includes (a) a limit on an absolute number of messages that a traffic group can store in the shared buffer space, and (b) a threshold relating to a degree of occupancy of the shared buffer space as a whole. The shared buffer space becomes congested when the bound is reached or exceeded. When a reserved buffer space reaches its predetermined state of congestion and the corresponding traffic group experiences shared space congestion, incoming messages associated with that traffic group are discarded. In the preferred embodiment, reserved buffer space congestion is defined relative to a given message, thus it is possible for a reserved buffer space to be filled to capacity yet not be in a state of congestion. In this instance, the controller is enabled to store messages in the shared buffer space.
The preferred embodiment is deployed the context of a connection-orientated communications protocol, such as the ATM protocol, wherein a traffic group comprises a group of virtual circuits associated with a single traffic class (hereinafter xe2x80x9cconnection groupxe2x80x9d). (In alternative embodiments traffic groups may comprise other types of digital traffic flows, not necessarily virtual circuits or connections.) Each reserved buffer space is preferably sized to provide a minimum guaranteed quality of service to the corresponding group of virtual connections. Under such circumstances, the shared buffer space can be viewed as an idle resource and the shared space access limit and threshold described above represent mechanisms for prioritizing this resource amongst connection groups and/or their associated traffic classes.
In the preferred embodiment, each connection group is further logically subdivided into one or more sub-groups. Each such sub-group is provisioned with a size threshold for the number of messages that the connections thereof may store in the memory. The reserved buffer space may become congested when the sub-group size threshold associated with a particular message is reached. That particular message may be discarded if the corresponding connection group experiences shared space congestion, otherwise the message may be stored in the shared buffer space. Defining multiple sub-groups within a connection group facilitates the provision of various message loss ratio guarantees since the probability of message loss is dependant upon the probability that the reserved buffer space assigned to the connection group is full (which is static for all subgroups) unioned with the probability that a sub-group size threshold is exceeded (which can be selected per sub-group). Messages which are placed within the shared buffer space thus represent service above the QoS level provided by corresponding reserved buffer space.
The sub-group size thresholds of a given connection group may define in aggregate a logical memory space larger than the physical buffer space allotted to the given connection group. This further enables the buffering system to take advantage of the bursty nature of many types of digital traffic.
In the preferred embodiment, connections within a connection group are also provisioned with a size threshold for the number of messages that may be stored in the memory. The reserved buffer space may become congested when the connection size threshold associated with a particular message is reached. That message may be discarded if the corresponding connection group experiences shared space congestion, otherwise the message may be stored in the shared buffer space. The connection size thresholds facilitate the isolation of non-conformant connection. If desired, connection size thresholds may be dynamically configured to be proportional to the weight of a given connection and inversely proportional to a sum of weights associated with a predefined group of connections having similar quality of service parameters.
In the preferred embodiment, either, or both, of the sub-group and connection size thresholds may apply to define congestion of the reserved buffer space for any given connection group. Thus messages will be discarded if the size threshold of a given connection is reached and/or the size threshold of the corresponding sub-group is reached, provided that shared space congestion is asserted against the corresponding connection group.
According to another aspect of the invention, a buffering system is provided for use in a communications device employing a connection-orientated communications protocol. The system includes a memory for storing digital messages associated with various connections, and a controller connected to the memory for determining whether to store or discard a given message based on predetermined discard criteria. The discard criteria includes the event that a given connection reaches an amount of stored messages equal to a dynamic maximum connection queue depth limit. This limit is proportional to a weight associated with the given connection and inversely proportional to a sum of weights associated with a predefined group of connections. For example, in an ATM system, an unspecified bit rate (UBR) connection has a weight defined by a minimum cell rate (MCR), and the predefined group of connections may include all active UBR connections, or only a subset thereof associated with a particular input or output port.